#include <iostream>
#include <vector>
using namespace std;


//输出vector内容
void Show(const vector<int>& v)
{
    for(int i=0;i<v.size();++i)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

//插入排序
void InsertSort(vector<int>& v)
{
   for(int i=0;i<v.size()-1;++i)
   {
        int end=i;
        int temp=v[end+1];
        while(end>=0)
        {
            if(temp<v[end])
            {
                v[end+1]=v[end];
                end--;
            }
            else
            break;
        }
        v[end+1]=temp;
   }
}

//希尔排序
void Shellsort(vector<int>& v)
{
    int gap=v.size();
    while(gap>1)
    {
        gap=gap/2;
        for(int i=0;i<v.size()-gap-1;++i)
        {
            int end=i;
            int temp=v[end+gap];
            while(end>=0)
            {
                if(temp<v[end])
                {
                    v[end+gap]=v[end];
                    end-=gap;
                }
                else
                break;
            }
            v[end+gap]=temp;
        }
    }
}

//选择排序
void SelectSort(vector<int>& v)
{
    for(int i=0;i<v.size();++i)
    {
        int star=i;
        int min=v[i];
        while(star<v.size())
        {
            if(v[min]>v[star])
                min=star;
            star++;
        }
        int temp=v[i];
        v[i]=v[min];
        v[min]=temp;
    }
}

//冒泡排序
void BubbleSort(vector<int>& v)
{
    for(int end=v.size()-1;end>=0;end--)
    {
        int exchange=0;
        for(int i=0;i<end;++i)
        {
            if(v[i+1]<v[i])
            {
                int temp=v[i];
                v[i]=v[i+1];
                v[i+1]=temp;
                exchange=1;
            }
        }
        if(exchange==0)
        break;
    }
}

//快速排序
void QukeSort(vector<int>& v,int begin,int end)
{
    if(begin>end) return;
    int left=begin;
    int right=end;
    int key=begin;
    while(left<right)
    {
        while(right>left&&v[right]>v[key])
        {
            right--;
        }
        while(right>left&&v[left]<v[key])
        {
            left--;
        }
        if(left<right)
        {
            int temp=v[left];
            v[left]=v[right];
            v[right]=temp;
        }
    }
    int meeti=left;
    int temp=v[meeti];
    v[meeti]=v[key];
    v[key]=temp;
    QukeSort(v,begin,meeti-1);
    QukeSort(v,meeti+1,end);
}
int main()
{
    vector<int> v(10);
    v={8,4,0,2,5,6,1,3,9,7};
    cout<<"排序前:"<<endl;
    Show(v);
    // cout<<"直接插入排序"<<endl;
    // InsertSort(v);
    // cout<<"希尔排序"<<endl;
    // Shellsort(v);
    // cout<<"选择排序"<<endl;
    // SelectSort(v);
    // cout<<"冒泡排序"<<endl;
    // BubbleSort(v);
    cout<<"快速排序"<<endl;
    QukeSort(v,0,v.size()-1);
    Show(v);
}